//
//  Problem712.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/2.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit
/*
 定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。

 示例 1:
     输入: s1 = "sea", s2 = "eat"
     输出: 231
     解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
     在 "eat" 中删除 "t" 并将 116 加入总和。
     结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。
 示例 2:
     输入: s1 = "delete", s2 = "leet"
     输出: 403
     解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
     将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
     结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
     如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。
 注意:
     0 < s1.length, s2.length <= 1000。
     所有字符串中的字符ASCII值在[97, 122]之间。
 */
@objcMembers class Problem712: NSObject {
    func solution() {
        print("cicsddawqxrotwfehpfzxjukgumtcplecvgumpfitwowmtuhlgcbssisieoqgsfvavvaordkzwxpnppfjurckhyzeugkjowqzvojzigkrehiapcsiwwhvchrzhcsdgqyaovqzgbicnsstcofnmiipqxmjldknkcojlhzdprkqrqzbybexhmcfxhezzbwbfcbvnxrhatlklhadltciubrubudxthujdhtipicnvgangdpqicshcmmoacaonfsssjujzkznmxamgvlmaleovrcqijsdhnr", "zkhkcdscdrgpqjqtksxiztcmymfgttiqntizhfafbvmjbjurxtbtnwilunqfmkkuvtgjzeoiunmqqbqoppejtzafjpbickphuvvmuhzvuxmsoeezvtlgfxjjjuwieobwldmyrfamokmewopvnmoiymfevorwanmicfumifjmrrhreeqkvmqgmwdfcmhxpujcbyfwdwqkbzovzuxzntwksedzzkdnqjpxhsqmffiwtxjedlbcpgfnetafbdxibsbntvqahhtbmbtdcgiedwdjnfbeqnydooasjdvxcyqqojiretcgeeycjrqqlxtuujmvzqrsrazvifeszibswkreosvzaexridrrcwptjavetgiiockenusrwsufnvskeumjiyvmyyadsqdwectoamfvpvcsalqtnpettilatie")
    }
    var ascii:[Character : Int] = [
            "a" : 97,
            "b" : 98,
            "c" : 99,
            "d" : 100,
            "e" : 101,
            "f" : 102,
            "g" : 103,
            "h" : 104,
            "i" : 105,
            "j" : 106,
            "k" : 107,
            "l" : 108,
            "m" : 109,
            "n" : 110,
            "o" : 111,
            "p" : 112,
            "q" : 113,
            "r" : 114,
            "s" : 115,
            "t" : 116,
            "u" : 117,
            "v" : 118,
            "w" : 119,
            "x" : 120,
            "y" : 121,
            "z" : 122
        ]
    func minimumDeleteSum(_ s1: String, _ s2: String) -> Int {
        if s1.count == 0, s2.count == 0 {
            return 0
        }
        
        var dp = Array(repeating: Array(repeating: -1, count: s2.count+1), count: s1.count+1)
        dp[s1.count][s2.count] = 0
        
        var s1Array:[Int] = Array(repeating: 0, count: s1.count)
        for (i, c) in s1.enumerated().reversed() {
            
            s1Array[i] = ascii[c]!
            if i == s1.count {
                continue
            }
            dp[i][s2.count] = dp[i+1][s2.count]  + ascii[c]!
        }
        
        var s2Array:[Int] = Array(repeating: 0, count: s2.count)
        for (i, c) in s2.enumerated().reversed() {
            s2Array[i] = ascii[c]!
            if i == s2.count {
                continue
            }
            dp[s1.count][i] = dp[s1.count][i+1]  + ascii[c]!
        }
        
        for (i, c1) in s1.enumerated().reversed() {
            if i == s1.count {
                continue
            }
            for (j, c2) in s2.enumerated().reversed() {
                if j == s2.count {
                    continue
                }
                if (c1 == c2) {
                    dp[i][j] = dp[i+1][j+1];
                } else {
                    dp[i][j] = min(dp[i+1][j] + ascii[c1]!, dp[i][j+1] + ascii[c2]!);
                }
            }
        }
        
        return dp[0][0]
    }
    
    func minimumDeleteSum1(_ s1: String, _ s2: String) -> Int {
            if s1.count == 0, s2.count == 0 {
                return 0
            }
            
            var dp = Array(repeating: Array(repeating: -1, count: s2.count+1), count: s1.count+1)
            dp[s1.count][s2.count] = 0
            for i in 1...s1.count {
                dp[s1.count - i][s2.count] = dp[s1.count - i + 1][s2.count]  + getAssii(s1, s1.count - i)
            }
            
            for i in 1...s2.count {
                dp[s1.count][s2.count - i] = dp[s1.count][s2.count - i + 1]  + getAssii(s2, s2.count - i)
            }
            
            var i = s1.count - 1
            while i >= 0 {
                var j = s2.count - 1
                while j >= 0 {
                    let assi = getAssii(s1, i)
                    let assj = getAssii(s2, j)
                    if (assi == assj) {
                        dp[i][j] = dp[i+1][j+1];
                    } else {
                        dp[i][j] = min(dp[i+1][j] + assi, dp[i][j+1] + assj);
                    }
                    j -= 1
                }
                i -= 1
            }
            
            return dp[0][0]
        }
        func getAssii(_ s: String, _ index: Int) -> Int {
            if index >= s.count {
                return 0
            }
            
            let sIndex = s.unicodeScalars.index(s.unicodeScalars.startIndex, offsetBy: index)
            return Int(s.unicodeScalars[sIndex].value)
        }
}
